//1089.复写零
// 时间复杂度O(N) 空间复杂度O(1)
//双指针
class Solution {
    public void duplicateZeros(int[] arr) {
        //1.先找到最后一个复写的数
        //(1)先判断cur的值
        //(2)决定dest向后移动一步还是两步
        //(3)判断一些dest是否已经到结束为止
        //(4)cur++
        int cur = 0;
        int dest = -1;
        int n = arr.length; 
        while (cur < n){
            if(arr[cur] != 0){
                  dest +=1;
            }else{
               dest += 2;
            }
            if(dest >= n-1){
                break;
            }
            cur++;
        }
       
        //2.处理边界情况  如果dest == n，说明arr[cur] == 0，并且最后一个0只能复写一次
        if(dest == n){
            arr[n-1] = 0;
            cur--;
            dest-=2;
        }
        //3.从后往前复写

        while(cur >= 0){
            if(arr[cur] != 0){
                arr[dest--] = arr[cur--];
                // dest--;
                // cur--;
             }else{
                arr[dest--] = 0;               
                arr[dest--] = 0;
                cur--;
            }
        }
       
    }
}